import numpy as np
import tree as tree


class MicroMouse(object):

    def __init__(self, cv, cell_len, bd, win, offset, map_size=32):
        self.cv = cv
        self.map_size = map_size
        self.cell_len = cell_len
        self.bd = bd
        self.win = win
        self.offset = offset
        self.after_id = None
        self.current_h = 0
        self.current_w = 0
        self.up = 0
        self.down = 1
        self.left = 2
        self.right = 3
        self.current_dir = self.right
        self.search_map = np.zeros((map_size, map_size, 4), dtype='int8')  # h/y, w/x, wall/up,down,left,right
        self.after_cancel = False
        # hand
        self.maze_map = None
        self.mouse_hand = None
        self.win_oval = None
        self.line_hand = []
        self.shortest_line_hane = []
        # search record
        self.searched_list = []   # [h/y, w/x]
        self.branch_list = []     # [h, w, dir]

    def draw_win_oval(self):
        # clear win point
        if self.win_oval is not None:
            self.cv.delete(self.win_oval)
        # draw win point
        w, h = self.win
        x, y = (w + 0.5) * self.cell_len + 3 * self.bd + self.offset, (h + 0.5) * self.cell_len + self.bd
        rate = self.cell_len / 3
        x0, y0 = x - rate, y - rate
        x1, y1 = x + rate, y + rate
        self.win_oval = self.cv.create_oval(x0, y0, x1, y1, fill='red')

    def draw_shortest_line(self, path):
        # clear win point
        for hane in self.shortest_line_hane:
            self.cv.delete(hane)
        # draw win point
        for point in path:
            h, w = point
            x, y = (w + 0.5) * self.cell_len + 3 * self.bd + self.offset, (h + 0.5) * self.cell_len + self.bd
            rate = self.cell_len / 5
            x0, y0 = x - rate, y - rate
            x1, y1 = x + rate, y + rate
            self.shortest_line_hane.append(self.cv.create_oval(x0, y0, x1, y1, fill='red'))

    def draw_mouse(self, w, h):
        """画电脑鼠"""
        if self.mouse_hand is not None:
            self.cv.delete(self.mouse_hand)
        x, y = (w + 0.5) * self.cell_len + 3 * self.bd + self.offset, (h + 0.5) * self.cell_len + self.bd
        rate = self.cell_len / 3
        # up
        if self.current_dir == self.up:
            x0, y0 = x - rate, y + rate
            x1, y1 = x + rate, y + rate
            x2, y2 = x, y - rate
        # down
        elif self.current_dir == self.down:
            x0, y0 = x - rate, y - rate
            x1, y1 = x + rate, y - rate
            x2, y2 = x, y + rate
        # left
        elif self.current_dir == self.left:
            x0, y0 = x + rate, y - rate
            x1, y1 = x + rate, y + rate
            x2, y2 = x - rate, y
        # right
        else:
            x0, y0 = x - rate, y - rate
            x1, y1 = x - rate, y + rate
            x2, y2 = x + rate, y
        self.mouse_hand = self.cv.create_polygon(x0, y0, x1, y1, x2, y2, fill='red')

    def draw_search_maze(self):
        # clear maze
        for tag in self.line_hand:
            self.cv.delete(tag)
        # draw maze
        for h in range(self.map_size):
            for w in range(self.map_size):
                for index in range(4):
                    # up and down for wall
                    if index in [self.up, self.down]:
                        x0 = w * self.cell_len + 3 * self.bd + self.offset
                        y0 = (h + index) * self.cell_len + self.bd
                        x1 = (w + 1) * self.cell_len + 3 * self.bd + self.offset
                        y1 = (h + index) * self.cell_len + self.bd
                    # left and right for wall
                    else:
                        x0 = (w + index - 2) * self.cell_len + 3 * self.bd + self.offset
                        y0 = h * self.cell_len + self.bd
                        x1 = (w + index - 2) * self.cell_len + 3 * self.bd + self.offset
                        y1 = (h + 1) * self.cell_len + self.bd
                    # no line draw white line
                    if self.search_map[h, w, index] == 1:
                        color = 'black'
                    else:
                        color = 'white'
                    # draw line
                    self.line_hand.append(self.cv.create_line(x0, y0, x1, y1, width=2, fill=color))

    def search_maze(self, mz):
        """search maze, get maze information"""
        self.maze_map = mz.get_maze_map()
        self.after_cancel = True
        self.by_step()

    def by_step(self):
        """search maze by step"""
        if self.after_cancel:
            # update search map, (maze's forward right left)
            point_info = self.update_search_map()
            # redraw search maze and win point
            self.draw_search_maze()
            self.draw_mouse(self.current_w, self.current_h)
            self.cv.update()
            # check forward and walk a step, do not walk back
            self.step_search_maze(point_info)
        # next step
        self.cv.after(1000, func=self.by_step())

    def step_search_maze(self, point_info):
        # mouse search maze
        # find exit point
        # if self.current_h == self.win[0] and self.current_w == self.win[1]:
        #     return
        # can choise dir
        # up
        if self.current_dir == self.up:
            point_info[self.down] = -1
        # down
        elif self.current_dir == self.down:
            point_info[self.up] = -1
        # left
        elif self.current_dir == self.left:
            point_info[self.right] = -1
        # right
        elif self.current_dir == self.right:
            point_info[self.left] = -1

        ccd = np.where(point_info==0)[-1]
        ccd_len = len(ccd)
        finded = False
        # have dir to go
        if ccd_len > 0:
            for dir_ in range(ccd_len):
                dir = ccd[dir_]
                # up
                if dir == self.up:
                    # not searched
                    if [self.current_h-1, self.current_w] not in self.searched_list:
                        # search first dir, other append to branch list
                        if not finded:
                            h, w, d = self.current_h-1, self.current_w, dir
                            finded = True
                        else:
                            self.branch_list.append([self.current_h, self.current_w, dir])
                # down
                elif dir == self.down:
                    # not searched
                    if [self.current_h+1, self.current_w] not in self.searched_list:
                        # search first dir, other append to branch list
                        if not finded:
                            h, w, d = self.current_h+1, self.current_w, dir
                            finded = True
                        else:
                            self.branch_list.append([self.current_h, self.current_w, dir])
                # left
                elif dir == self.left:
                    # not searched
                    if [self.current_h, self.current_w-1] not in self.searched_list:
                        # search first dir, other append to branch list
                        if not finded:
                            h, w, d = self.current_h, self.current_w-1, dir
                            finded = True
                        else:
                            self.branch_list.append([self.current_h, self.current_w, dir])
                # right
                elif dir == self.right:
                    # not searched
                    if [self.current_h, self.current_w+1] not in self.searched_list:
                        # search first dir, other append to branch list
                        if not finded:
                            h, w, d = self.current_h, self.current_w+1, dir
                            finded = True
                        else:
                            self.branch_list.append([self.current_h, self.current_w, dir])
            # has search dir, but all have searched
            if not finded:
                if len(self.branch_list) > 0:
                    self.current_h, self.current_w, self.current_dir = self.branch_list[-1]
                    self.branch_list.pop()
                else:
                    print('search complete!')
                    self.find_shortest_path(np.copy(self.search_map))
            # at last have one dir have no search
            else:
                self.current_h, self.current_w, self.current_dir = h, w, d
        # not dir to go, back to branch
        else:
            if len(self.branch_list) > 0:
                self.current_h, self.current_w, self.current_dir = self.branch_list[-1]
                self.branch_list.pop()
            else:
                print('search complete!')
                self.find_shortest_path(np.copy(self.search_map))
        # record searched list
        self.searched_list.append([self.current_h, self.current_w])

    def update_search_map(self):
        # update search map current position, (maze's forward right left)
        point_info = np.copy(self.maze_map[self.current_h][self.current_w])
        self.search_map[self.current_h][self.current_w] = point_info
        # update search map adjoin position, border control
        if self.current_dir in [self.up, self.down]:
            # up
            if self.current_dir == self.up and self.current_h > 0:
                self.search_map[self.current_h - 1][self.current_w][self.down] = point_info[self.up]
            # down
            elif self.current_dir == self.down and self.current_h < (self.map_size-1):
                self.search_map[self.current_h + 1][self.current_w][self.up] = point_info[self.down]
            # left and right
            if self.current_w > 0:
                self.search_map[self.current_h][self.current_w - 1][self.right] = point_info[self.left]
            if self.current_w < (self.map_size-1):
                self.search_map[self.current_h][self.current_w + 1][self.left] = point_info[self.right]
        else:
            # left
            if self.current_dir == self.left and self.current_w > 0:
                self.search_map[self.current_h][self.current_w - 1][self.right] = point_info[self.left]
            # right
            if self.current_dir == self.right and self.current_w < (self.map_size-1):
                self.search_map[self.current_h][self.current_w + 1][self.left] = point_info[self.right]
            # up and down
            if self.current_h > 0:
                self.search_map[self.current_h - 1][self.current_w][self.down] = point_info[self.up]
            if self.current_h < (self.map_size-1):
                self.search_map[self.current_h + 1][self.current_w][self.up] = point_info[self.down]
        return point_info

    def find_shortest_path(self, search_map):
        """find shortest path"""
        arrived_points = [[0, 0]]    # [h, w]
        edge_trees = []
        shortest_path = []           # [h, w]
        # root tree
        root = tree.Tree()
        root.h = 0
        root.w = 0
        edge_trees.append(root)

        while len(edge_trees) > 0:
            append_trees = []
            delete_trees = []
            # all edge point to next step
            for edge_tree in edge_trees:
                # one edge point to next step
                point_info = search_map[edge_tree.h][edge_tree.w]
                # current point can go to dirs,  have dir(append)  or  not have dir(delete)
                dirs = list(np.where(point_info == 0)[-1])
                if len(dirs) > 0:
                    for dir in dirs:
                        if dir == self.up:
                            h, w = edge_tree.h-1, edge_tree.w
                        elif dir == self.down:
                            h, w = edge_tree.h+1, edge_tree.w
                        elif dir == self.left:
                            h, w = edge_tree.h, edge_tree.w-1
                        else:
                            h, w = edge_tree.h, edge_tree.w+1
                        # not go to this point before
                        if [h, w] not in arrived_points:
                            append_trees.append(tree.Tree())
                            append_trees[-1].last_tree = edge_tree
                            append_trees[-1].h = h
                            append_trees[-1].w = w
                            arrived_points.append([h, w])
                            # find win point
                            if h == self.win[0] and w == self.win[1]:
                                edge_tree_ = append_trees[-1]
                                while edge_tree_.last_tree is not None:
                                    shortest_path.append([edge_tree_.h, edge_tree_.w])
                                    edge_tree_ = edge_tree_.last_tree
                                self.draw_shortest_line(shortest_path)
                                return shortest_path
                else:
                    delete_trees.append(edge_tree)
            # append
            for edge_tree in append_trees:
                edge_trees.append(edge_tree)
            # delete
            for delete_tree in delete_trees:
                edge_trees.remove(delete_tree)
        return shortest_path

    def reset_mouse(self):
        # reset mouse
        self.after_cancel = False
        self.current_h = 0
        self.current_w = 0
        self.current_dir = self.right
        self.searched_list = []
        self.searched_list = []
        self.branch_list = []
        self.search_map = np.zeros((self.map_size, self.map_size, 4), dtype='int8')
        self.draw_search_maze()
        self.draw_mouse(self.current_w, self.current_h)
